package com.company.test27_28;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * Created by Administrator on 2016.11.8.
 */
public abstract class AbstractGraph<V> implements Graph<V> {
    protected List<V> vertices;
    protected List<List<Integer>> neighbors;

    protected AbstractGraph(int[][] edges,List<V> vertices){
        this.vertices=vertices;
        createAdjacencyLists(edges,vertices.size());
    }

    protected AbstractGraph(List<Edge> edges,V[] vertices){
        this.vertices=new ArrayList<V>();
        for(int i=0;i<vertices.length;i++) {
            this.vertices.add(vertices[i]);
        }
        createAdjacencyLists(edges,vertices.length);
    }

    protected AbstractGraph(int[][] edges,V[] vertices){
        this.vertices=new ArrayList<V>();
        for(int i=0;i<vertices.length;i++) {
            this.vertices.add(vertices[i]);
        }
        createAdjacencyLists(edges,vertices.length);
    }

    protected AbstractGraph(List<Edge> edges,List<V> vertices){
        this.vertices=vertices;
        createAdjacencyLists(edges,vertices.size());
    }

    protected AbstractGraph(List<Edge> edges,int numberOfVertices){
        vertices=new ArrayList<V>();
        for(int i=0;i<numberOfVertices;i++){
            vertices.add((V)(new Integer(i)));
        }
        createAdjacencyLists(edges,vertices.size());
    }

    protected AbstractGraph(int[][] edges,int numberOfVertices){
        vertices=new ArrayList<V>();
        for(int i=0;i<numberOfVertices;i++){
            vertices.add((V)(new Integer(i)));
        }
        createAdjacencyLists(edges,vertices.size());
    }

    private void createAdjacencyLists(int[][] edges,int numberOfVertices){
        neighbors=new ArrayList<>();
        for(int i=0;i<numberOfVertices;i++){
            neighbors.add(new ArrayList<>());
        }

        for(int i=0;i<edges.length;i++){
            int u=edges[i][0];
            int v=edges[i][1];
            neighbors.get(u).add(v);
        }
    }

    private void createAdjacencyLists(List<Edge> edges,int numberOfVertices){
        neighbors=new ArrayList<>();
        for(int i=0;i<numberOfVertices;i++){
            neighbors.add(new ArrayList<>());
        }

        for(Edge edge:edges){
            neighbors.get(edge.u).add(edge.v);
        }
    }

    @Override//返回点的数量
    public int getSize(){
        return vertices.size();
    }

    @Override//返回所有的点组成的数组
    public List<V> getVertices(){
        return vertices;
    }

    @Override//返回相应下标的点
    public V getVertex(int index){
        return vertices.get(index);
    }

    @Override//返回相应点的下标
    public int getIndex(V v){
        return vertices.indexOf(v);
    }

    @Override//返回相应下表的所有邻居
    public List<Integer> getNeighbors(int index) {
        return neighbors.get(index);
    }

    @Override//返回相应点的度
    public int getDegree(int v) {
        return neighbors.get(v).size();
    }

    @Override//返回邻接矩阵
    public int[][] getAdjacencyMatrix() {
        int[][] adjacencyMatrix=new int[getSize()][getSize()];

        for (int i=0;i<neighbors.size();i++){
            for(int j=0;j<neighbors.get(i).size();j++){
                adjacencyMatrix[i][neighbors.get(i).get(j)]=1;
            }
        }
        return adjacencyMatrix;
    }

    @Override//打印邻接矩阵
    public void printAdjacencyMatrix() {
        int[][] adjacencyMatrix=getAdjacencyMatrix();

        for (int[] anAdjacencyMatrix : adjacencyMatrix) {
            for (int anAnAdjacencyMatrix : anAdjacencyMatrix) {
                System.out.print(anAnAdjacencyMatrix + " ");
            }
            System.out.println();
        }
    }

    //返回哈密顿路径,如果不存在哈密顿路径，则返回null
    public List<Integer> getHamiltonianPath(V vertex){
        return getHamiltonianPath(getIndex(vertex));
    }
    public List<Integer> getHamiltonianPath(int v){
        //返回一个从点v开始的哈密顿路径，应用的是深度优先搜索。
        int[] next=new int[getSize()];
        for(int i=0;i<next.length;i++){
            next[i]=-1;
        }

        boolean[] isVisited=new boolean[getSize()];
        List<Integer> result=null;

        for(int i=0;i<getSize();i++){
            reorderNeigborsBasedOnDegree(neighbors.get(i));
        }

        if(getHamiltonianPath(v,next,isVisited,v,1)){
            int current=v;
            result=new ArrayList<>();
            while (current!=-1){
                result.add(current);
                current=next[current];
            }
            result.add(v);
        }
        return result;
    }

    //对某一个点的邻居进行度的排序
    private void reorderNeigborsBasedOnDegree(List<Integer> list){
        for(int i=list.size()-1;i>=1;i--){
            int currentMaxDegree=getDegree(list.get(0));
            int currentMaxIndex=0;

            for(int j=1;j<=i;j++){
                if(currentMaxDegree<getDegree(list.get(j))){
                    currentMaxDegree=getDegree(list.get(i));
                    currentMaxIndex=j;
                }
            }
            if (currentMaxIndex!=i){
                int temp=list.get(currentMaxIndex);
                list.set(currentMaxIndex,list.get(i));
                list.set(i,temp);
            }
        }
    }

    //如果所有的点都被访问过了，则返回true
    protected boolean allVisited(boolean[] isVisited){
        boolean result=true;
        for (int i=0;i<getSize();i++){
            result=result&&isVisited[i];
        }

        return result;
    }

    //对v进行哈密顿搜索，若成功则返回true
    private boolean getHamiltonianPath(int v,int[] next,boolean[] isVisited,int HEAD,int deep){
        isVisited[v]=true;
        if (deep==isVisited.length){
            System.out.println("get");
            List<Integer> neighbor=neighbors.get(v);
            for(int i=0;i<neighbor.size();i++){
                if(neighbor.get(i)==HEAD)
                    return true;
            }
            isVisited[v]=false;
            return false;
        }
        for(int i=0;i<neighbors.get(v).size();i++){
            int u=neighbors.get(v).get(i);
            if(!isVisited[u]&&getHamiltonianPath(u,next,isVisited,HEAD,deep+1)){
                next[v]=u;
                return true;
            }
        }

        isVisited[v]=false;
        return false;
    }

    @Override//输出所有的边
    public void printEdges() {
        for(int u=0;u<neighbors.size();u++){
            System.out.print("Vertex"+u+":");
            for(int v=0;v<neighbors.get(u).size();v++){
                System.out.print(neighbors.get(u).get(v)+" ");
            }
            System.out.println();
        }
    }

    //边类
    public static class Edge implements Graph.Edge{
        private int u;
        private int v;

        @Override
        public int getU() {
            return u;
        }

        @Override
        public int getV() {
            return v;
        }

        public Edge(int u, int v){
            this.u=u;
            this.v=v;
        }
    }

    @Override//广度优先搜索
    public SpanningTree bfs(int v) {
        List<Integer> searchOrder=new ArrayList<>();
        int[] parent=new int[getSize()];
        for(int i=0;i<getSize();i++) {
            parent[i] = -1;
        }
        LinkedList<Integer> queue=new LinkedList<>();
        boolean[] isVisited=new boolean[getSize()];
        isVisited[v]=true;
        queue.offer(v);

        while (!queue.isEmpty()){
            int u=queue.pop();
            searchOrder.add(u);
            for(int i=0;i<neighbors.get(u).size();i++){
                int point=neighbors.get(u).get(i);
                if(!isVisited[point]){
                    queue.offer(point);
                    parent[point]=u;
                    isVisited[point]=true;
                }
            }
        }

        return new SpanningTree(v,parent,searchOrder);
    }

    @Override//深度优先搜索
    public SpanningTree dfs(int v) {
        int[] parent=new int[getSize()];
        List<Integer> searchOrder=new LinkedList<>();
        for(int i=0;i<parent.length;i++){
            parent[i]=-1;
        }
        dfs(v,parent,searchOrder,new boolean[getSize()]);

        return new SpanningTree(v,parent,searchOrder);
    }
    private void dfs(int u, int[] parent, List<Integer> searchOrder, boolean[] isVisited){
        searchOrder.add(u);
        isVisited[u]=true;
        for(int i=0;i<neighbors.get(u).size();i++){
            int point=neighbors.get(u).get(i);
            if(!isVisited[point]){
                parent[point]=u;
                dfs(point,parent,searchOrder,isVisited);
            }
        }
    }

    //生成树
    public class SpanningTree implements Graph.SpanningTree{
        private int root;
        private int[] parent;
        private List<Integer> searchOrders;

        SpanningTree(int root, int[] parent, List<Integer> searchOrders){
            this.root=root;
            this.parent=parent;
            this.searchOrders=searchOrders;
        }

        public SpanningTree(int root,int[] parent){
            this(root,parent,null);
        }

        public int getRoot(){
            return root;
        }

        public int getParent(int v){
            return parent[v];
        }

        public List<Integer> getSearchOrders(){
            return searchOrders;
        }

        public int getNumberOfVerticesFound(){
            return searchOrders.size();
        }

        public List<V> getPath(int index){
            ArrayList<V> path=new ArrayList<V>();

            do{
                path.add(vertices.get(index));
                index=parent[index];
            }while (index!=-1);

            return path;
        }

        public void printPath(int index){
            List<V> path=getPath(index);
            System.out.println("A path from "+vertices.get(root)+" to "+vertices.get(index)+":");
            for(int i=path.size()-1;i>=0;i--){
                System.out.print(path.get(i)+" ");
            }
        }

        public void printTree(){
            System.out.println("Root is:"+vertices.get(root));
            System.out.print("Edges:");
            for(int i=0;i<parent.length;i++){
                if(parent[i]!=-1){
                    System.out.print("("+vertices.get(parent[i])+","+vertices.get(i)+")");
                }
            }
            System.out.println();
        }
    }

    @Override//测试这个图是否为一个二部图
    public boolean isBipartite() {
        if(neighbors==null){
            return false;
        }
        boolean[] one=new boolean[getSize()];
        boolean[] two=new boolean[getSize()];
        LinkedList<Integer> que=new LinkedList<>();

        //对每一个环进行处理，环中出现非二部的情况，则返回false
        for(int i=0;i<getSize()&&!one[i]&&!two[i];i++){
            que.offer(i);
            one[i]=true;
            while (!que.isEmpty()){
                int current=que.poll();
                List<Integer> neighbor=neighbors.get(current);
                for(int j=0;j<neighbor.size();j++){
                    if(one[current]){
                        if(one[neighbor.get(j)]){
                            return false;
                        }else if(!two[neighbor.get(j)]){
                            two[neighbor.get(j)]=true;
                            que.offer(neighbor.get(j));
                        }
                    }else {
                        if(two[neighbor.get(j)]){
                            return false;
                        }else if(!one[neighbor.get(j)]){
                            one[neighbor.get(j)]=true;
                            que.offer(neighbor.get(j));
                        }
                    }
                }
            }
        }
        return true;
    }

    @Override//增加一个点
    public boolean add(V vertex) {
        if(vertices.indexOf(vertex)!=-1){
            vertices.add(vertex);
            return true;
        }
        return false;
    }

    @Override//删除一个点
    public boolean remove(V vertex) {
        int current=vertices.indexOf(vertex);
        if(current==-1){
            return false;
        }
        vertices.remove(current);
        neighbors.remove(current);
        for(List<Integer> neighbor:neighbors){
            for(int j=0;j<neighbor.size();j++){
                if(neighbor.get(j)>current){
                    neighbor.set(j,neighbor.get(j)-1);
                }else if(neighbor.get(j)==current){
                    neighbor.remove(j);
                    j--;
                }
            }
        }
        return true;
    }

    @Override//增加一条边
    public boolean add(Graph.Edge edge) {
        if (edge.getU()>=neighbors.size()||edge.getU()<0){
            return false;
        }

        if(edge.getV()>=neighbors.size()||edge.getV()<0){
            return false;
        }

        for(int i=0;i<neighbors.get(edge.getU()).size();i++){
            if(neighbors.get(edge.getU()).get(i)==edge.getV()){
                return false;
            }
        }

        neighbors.get(edge.getU()).add(edge.getV());
        return true;
    }

    @Override//删除一条边
    public boolean remove(Graph.Edge edge) {
        if (edge.getU()>=neighbors.size()||edge.getU()<0){
            return false;
        }

        for(int i=0;i<neighbors.get(edge.getU()).size();i++){
            if(neighbors.get(edge.getU()).get(i)==edge.getV()){
                neighbors.get(edge.getU()).remove(i);
                return true;
            }
        }
        return false;
    }
}